// 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
// 返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

// 解题思路：

// 按照正常的思路，首先从头到尾遍历链表，拷贝每个节点的 value 和 next 指针。
// 然后从头再次遍历，第二次遍历的目的在于拷贝每个节点的 sibling 指针。

// 然而即使找到原节点的 sibling 指针，还是得为了找到复制节点对应的 sibling 指针而再遍历一遍。
// 那么对于 n 个要寻找 sibling 指针的节点，复杂度就是 O(N\*N)。

// 显然，为了降低复杂度，必须从第二次遍历着手。这里采用的方法是，在第一次遍历的时候，
// 把 (原节点, 复制节点) 作为映射保存在表中。那么第二次遍历的时候，就能在 O(1) 的复杂度下立即找到原链上 sibling 指针在复制链上对应的映射。

/*function RandomListNode(x){
    this.label = x;
    this.next = null;
    this.random = null;
}*/

function Clone(pHead) {
  // write code here
  if (!pHead || !pHead.next) {
    return pHead;
  }
  const map = new Map();
  let node = pHead;
  const newHead = new RandomListNode(node.label);
  let newNode = newHead;
  map.set(node, newNode);

  while (node.next) {
    newNode.next = new RandomListNode(node.next.label);
    node = node.next;
    newNode = newNode.next;
    map.set(node, newNode);
  }
  newNode = newHead;
  node = pHead;
  while (newNode) {
    newNode.random = map.get(node.random);
    newNode = newNode.next;
    node = node.next;
  }
  return newHead;
}
